A. Field of the Invention
The present invention relates generally to data processing and, more particularly, to reordering of information that arrives in an out-of-order sequence after transmission.
B. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was turned on.
To meet the new demands, purpose-built routers were architected. Purpose-built routers are designed and built with components optimized for routing. They not only handled higher line rates and higher network traffic volume, they also added functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A switching fabric or other transmission medium may be implemented in the router to carry the packets between the ports. In a high-performance purpose-built router, the switching fabric may transmit a large amount of information between a number of internal components. Typically, the information is transmitted in discrete quantities called packets, or broken down even further into a series of cells.
One property of the switching fabric is that, even though it may have enough bandwidth to handle its cell traffic, cells transmitted to a particular destination may arrive at that destination in an out-of-order sequence. Thus, although a first cell may be transmitted before a second cell, the second cell may be received before the first cell. Generally, the order of the received cells is important and should be preserved.
Reorder circuits may be used to reorder cells received from a particular source into their correct transmission order. Essentially, each cell, as it is transmitted from a source, is appended with a sequence number. The reorder circuits examine the received sequence numbers to determine the correct cell order. In the situation in which there are multiple possible sources, such as, for example, in a switching fabric that cross-connects a large number of sources, a corresponding large number of reorder circuits are required. This can be inefficient, both because of the large hardware requirements of all the reorder circuits and because while the reorder circuits dedicated to certain sources may be running at maximum capacity, the reorder circuits dedicated to other sources may be sitting idle.
Thus, there is a need in the art to more efficiently implement the functionality performed by multiple reorder circuits that reorder information received from multiple sources.